Computer and information system security is currently an important issue. With the proliferation of computers and computer networks into all aspects of business and daily life—financial, medical, education, government, and communications—the concern over secure file access and communications privacy is growing.
Publicly accessible secure database systems pose significant security problems. Attempts to achieve high levels of technical invulnerability may lead to practical problems, system weaknesses and security holes. Passwords may be written near access terminals. Security tokens can be stolen or misplaced. Users may share supposedly secret information. Administration capability bypasses normal security protocols. Secure systems may be built on insecure platforms. Therefore, it is desirable to maintain private information in secure format, without relying on trust of any party who does not require access to the private information, up to a point where it is used by the intended recipient of the information.
The liability or risks involved in holding or communicating private information can well exceed the value of the storage or communications services. Therefore, even in the case of a trusted party, indemnification or insurance may be inefficient or insufficient means for addressing these risks or liabilities. Rather, where considerable risk or liability arises from unauthorized disclosure of the information, the storage or communication of the information must involve an efficient scheme that will minimize the risk of disclosure. Therefore, an intermediary in a transaction preferably handles only encrypted data, and need not be trusted to maintain the privacy of the underlying message. While two-party encryption is well known, schemes are not well developed for providing third party involvement, wherein the third party plays a requisite role in the transaction but which need not or is not trusted with access to the information or the cryptographic key.
A number of communications systems and methods are known for dealing with three-party communications, for example, where a third party provides ancillary services to support the communications, such as authentication, accounting, and key recovery. Often, the nature of these communications protocols places the third party (or group of third parties) in a position of trust, meaning that the third party or parties, without access to additional information, can gain access to private communications or otherwise undermine transactional security or privacy.
Transactions for which third party support may be appropriate include distribution of private medical records, communication of digital content, and anonymous proxy services.
Another aspect of three party communications is that it becomes possible for two (or more) parties to hold portions of a secret or a key to obtain the secret, without any one party alone being able to access the secret. For example, Silvio Micali has developed a mature Fair Encryption scheme in which a number of trustees collaborate to hold portions of a key used to secure privacy of a communication between two principals, but who must act together to gain access to the secret. In Micali's Fair Encryption scheme, however cooperation of neither of the principal parties to a communication is required in order to access the secret. The third party trustees, as a group, are trusted with a secret. The basis for this trust is an issue of factual investigation. The Micali Fair Encryption scheme does, however, provide a basis for the generation and use of composite asymmetric encryption keys. See, Eyal Kushilevitz, Silvio Micali & Rafael Ostrovsky, “Reducibility and Completeness in Multi-Party Private Computations”, Proc. of 35th FOCS, pp. 478–489, 1994, expressly incorporated herein by reference.
The Micali Fair Encryption scheme does not, however, allow communication of a secret in which only one party gains access to the content, and in which the third party or parties and one principal operate only on encrypted or secret information. This system is discussed in further detail below.
See: S. Micali. Fair Public-Key Cryptosystems. Advances in Cryptology—Proceedings of CRYPTO '92 (E. F. Brickell, ed.) Lecture Notes in Computer Science 740, SpringerVerlag (1993) pages 113–138; S Micali, Fair cryptosystems, MIT Technical Report, MIT/LCS/TR-579, November 1993, MIT Laboratory for Computer Science, November 1993.
See also, N. Gilboa, “Two Party RSA Key Generation”, Proc of Crypto '99, Lecture Notes in Computer Science, Vol. 1666, Springer-Verlag, pp. 116–129, 1999; D. Boneh, J. Horwitz, “Generating a product of three primes with an unknown factorization”, Proc. of the third Algorithmic Number Theory Symposium (ANTS), 1998, pp. 237–251; Lin, Cun-Li, Sun, Hung-Min, and Hwang, Tzonelih, “Three Party Key Exchange: Attacks and a Solution”.
Electronic Medical Records
In the field of medical care, accuracy of collected data is of significant importance. Erroneous data, whether collected manually or automatically, presents the possibility of an erroneous diagnosis or treatment. Prior accumulated data about the patient may be relevant to future diagnosis and treatment. Therefore, preservation and availability of accurate medical records remains an important part of the modern health care system.
The art of medical record keeping has developed over centuries of medical practice to provide an accurate account of a patient's medical history. Record keeping in medical practice was developed to help physicians, and other healthcare providers, track and link individual “occurrences” between a patient and a healthcare provider. Each physician/patient encounter may result in a record including notes on the purpose of the visit, the results of physician's examination of the patient, and a record of any drugs prescribed by the physician. If, for example, the patient were referred to another clinic for additional testing, such as a blood analysis, this would form a separate medical encounter, which would also generate information for the medical record.
Over the years, paper medical records have evolved from individual practitioners' informal journals to the current multi-author, medical/legal documents. These paper records serve as the information system on which modern medical practice is based. While the paper-based medical record system has functioned well over many decades of use, it has several shortcomings. First, while a paper-based record system can adequately support individual patient-physician encounters, it is cumbersome to use as a source of pooled data for large-scale analysis. While the medical data in the paper-based records is substantial, the ability to adequately index, store and retrieve information from the paper-based mechanisms prevents efficient analysis of the data. Thus, paper medical records could be a rich source of information for generating new knowledge about patient care, if the data could be accessed on a large scale. Second, each portion of the paper-based record is generated and kept at the site of the medical service. Hence, the total record is fragmented among many sites. Consequently, access by off-site physicians is less than optimal. The inability to access a complete medical record in a short period of time presents problems both for individual care and group care of patients. Thus, electronic medical records (EMRs) have been developed to facilitate storage, retrieval, communication and use of the valuable patient medical history information, both for the particular patient and for studies of patient populations.
While there have been attempts to develop computer database architectures capable of storing and retrieving medical record information which reconcile physicians' desires for maintaining a format of unstructured medical information with database requirements for highly structured data storage, these systems provide an inadequate infrastructure for the efficient transmission, use and security protection of the data.
Medical information poses significant challenges to knowledge management systems. Medical information presently includes file types including various media types, including numeric data, text, scanned text images, scanned graphic images, sound (e.g., phonocardiography and dictation), high resolution images (radiology) and video (ultrasonic imaging and fluoroscopy).
The medical records for an individual may, over time, grow to multiple megabytes or even gigabytes of data, and advanced medical techniques promise to increase the volume of available data. These records come from a number of different medical service providers, and may be stored in geographically disparate locations. Often, a new medical service provider will seek to review all appropriate previous medical records for a patient. Further, in third party reimbursement situations, the third party payor will seek to review records in connection with billed services. These various data types and associated information storage systems are not standardized, impeding efficiency of sharing and communicating the data.
Medical records often include data that is intensely personal, such as sexual habits, drug abuse, psychological disorders, family histories, genetics, terminal diseases, injuries, and the like. This personal information is revealed to, or generated by, treating medical professionals in an environment that presumes an absolute privilege held by the patient. The adoption of electronic medical record systems should not impair this presumption. Thus, while there are legitimate reasons for transmitting medical information files, such transmission must be secure, limited to appropriate circumstances and to authorized recipients.
Indeed, while the private medical information technically cannot be disclosed without the consent of the patient, since at least the time of Hippocrates, the medical institutions that hold this information guard it jealously. Thus, privacy considerations may make it difficult to obtain collaboration between medical institutions in the ongoing treatment of a patient. While there are important legitimate uses for medical data, there is also a substantial possibility for abuse of the data and the associated trust relationship between patient and medical care provider represented therein. Presently, laws and regulations have been promulgated (but not yet effective) regulating electronic medical records.
The U.S. Supreme Court has reaffirmed that the expectation of privacy of medical data is necessary in order to ensure that patients are not deterred from seeking needed medical care. Disclosure of medical information to non-medical personnel without patient consent was a primary concern of the Court. Ferguson v. City of Charleston, No. 99–936. Argued Oct. 4, 2000—Decided Mar. 21, 2001.
Typically, in a hospital medical information system, information relating to patients in a database is generated and used by users having a variety of roles, including doctors and medical professionals of various specialties, nurses, therapists of various types, paraprofessionals, social workers, clinical laboratories, and bedside devices (which may automatically generate or receive patient information). In addition, medical information is used, but typically not generated by, pharmacies, administrators, lawyers, insurers or payors, and other parties. Because of the many types of caregivers and other data users, the idea of role-based access is appropriate; basically, medical professionals of different types will require access to various subsets of the medical record. For example, typically the primary care physician and certain consults will require full access, while others may not require full access.
One scheme for increasing the portability of medical records is to provide personal data storage devices, for example in credit card format optical storage medium. These devices, however, present a security risk, since it cannot be presumed that the patient will be able to provide consent to the use of the information when required; thus, access controls should contemplate that scenario. Further, the information carrier can be lost, unavailable or stolen.
Encryption Technologies
Encryption technologies, particularly public key encryption systems, seek to minimize some of these weaknesses by reducing the need to share secrets amongst participants to a secure or private communication. Typical public key encryption technologies, however, presume that a pair of communications partners seek to communicate directly between each other, without the optional or mandatory participation of a third party, and, in fact, are designed specifically to exclude third party monitoring. Third parties, however, may offer valuable services to the participants in a communication, but existing protocols for involvement of more than two parties are either inefficient or insecure.
Traditional encryption algorithm schemes rely on use of one or more finite keys which are provided to an algorithm which generates a data string which is apparently random, called pseudorandom, but which can be predicted based on a knowledge of both the algorithm and the key(s), allowing extraction of a superimposed data message. Optimality of an algorithm for a given set of circumstances is based on a number of factors, and therefore many different cryptographic schemes coexist. Essentially, the key should be sufficiently long and stochastic that an extraordinarily long period of time would be necessary to attempt a brute force attack on the algorithm, while only a reasonable amount of time is required to generate keys, encrypt and decrypt messages. In addition, the key should be sufficiently long that observation of pseudorandom (encrypted) datastreams does not permit one to determine the key to the algorithm.
Public Key Encryption is a concept wherein two keys are provided. The keys form a pair, such that a message encrypted with one key of the pair may be decrypted only by the corresponding key, but knowledge of the public key does not impart effective knowledge of the private key. Typically, one of the keys is made public, while the other remains secret, allowing use for both secure communications and authentication. Communications may include use of multiple key pairs, to provide bilateral security. The public key pair may be self-generated, and therefore a user need not transmit the private key. It must, however, be stored.
The basis for Diffie Hellman and RSA-type public key encryption methods is the large disparity in computational complexity between decrypting the public key created cipher text with the public key encryption private key, which is very rapid and simple to do, and working through the possibilities without the key, which takes a very long time through all known means.
Modern public-key data encryption was originally suggested by Diffie and Hellman, “New Directions In Cryptography,” I.E.E.E. Transactions on Information Theory (November 1976) (the disclosure of which is hereby incorporated by reference), and was further developed by Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman: “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM 21(2):120–126 (February 1978) (the disclosure of which is hereby incorporated by reference). See also, U.S. Pat. No. 4,351,982, expressly incorporated herein by reference.
The basic reason for public-key encryption system is to ensure both the security of the information transferred along a data line, and to guarantee the identity of the transmitter and to ensure the inability of a receiver to “forge” a transmission as being one from a subscriber on the data line. Both of these desired results can be accomplished with public-key data encryption without the need to maintain a list of secret keys specific to each subscriber on the data line, and without requiring the periodic physical delivery or the secure electronic transmission of secret keys to the various subscribers on the data line.
According to the Diffie Hellman scheme, two hosts can create and share a secret key without ever communicating the key. Each host receives the “Diffie-Hellman parameters”. A prime number, ‘p’ (larger than 2) and “base”, ‘g’, an integer that is smaller than ‘p’. The hosts each secretly generate their own private number, called ‘x’, which is less than “p−1”. The hosts next generate a respective public key, ‘y’. They are created with the function: y=gx Mod p. The two hosts now exchange their respective public keys (‘y’) and the exchanged numbers are converted into a secret key, ‘z’ by the following function: z=yx Mod p. ‘z’ can now be used as an encryption key in a symmetric encryption scheme. Mathematically, the two hosts should have generated the same value for ‘z’, since according to mathematical identity theory,z=(gx Mod p)x′Mod p=(gx′Mod p)x Mod p. 
A method of public-key encryption developed by Rivest, Shamir & Adelman, and now generally referred to as RSA, is based upon the use of two extremely large prime numbers which fulfill the criteria for the “trap-door, one-way permutation.” Such a permutation function enables the sender to encrypt the message using a non-secret encryption key, but does not permit an eavesdropper to decrypt the message by crypto-analytic techniques within an acceptably long period of time. This is due to the fact that for a composite number composed of the product of two very large prime numbers, the computational time necessary to factor this composite number is unacceptably long. A brute force attack requires a sequence of putative keys to be tested to determine which, if any, is appropriate. Therefore a brute force attack requires a very large number of iterations. The number of iterations increases geometrically with the key bit size, while the normal decryption generally suffers only an arithmetic-type increase in computational complexity.
In the RSA encryption algorithm, the message (represented by a number M) is multiplied by itself (e) times (called “raising (M) to the power (e)”), and the product is then divided by a modulus (n), leaving the remainder as a ciphertext (C): C=Me mod n. In the decryption operation, a different exponent, (d) is used to convert the ciphertext back into the plain text: M=Cd mod n. The modulus (n) is a composite number, constructed by multiplying two prime numbers, (p) and (q), together: n=p*q. The encryption and decryption exponents, (d) and (e), are related to each other and the modulus (n) in the following way: d=e−1 mod ((p−1) (q−1)), or equivalently, d*e=1 mod ((p−1) (q−1)). The RSA ciphertext is thus represented by the expression C=Me mod n. The associated decryption function is M=Cd mod n. Therefore, M=Cd mod n=(Me mod n)d mod n, indicating that the original message, encrypted with one key, is retrieved as plain text using the other key. To calculate the decryption key, one must know the numbers (p) and (q) (called the factors) used to calculate the modulus (n).
The RSA Algorithm may be divided, then, into three steps:                (1) key generation: in which the factors of the modulus (n) (the prime numbers (p) and (q)) are chosen and multiplied together to form (n), an encryption exponent (e) is chosen, and the decryption exponent (d) is calculated using (e), (p), and (q).        (2) encryption: in which the message (M) is raised to the power (e), and then reduced modulo (n).        (3) decryption: in which the ciphertext (C) is raised to the power (d), and then reduced modulo (n).        
Micali, U.S. Pat. Nos. 6,026,163 and 5,315,658, expressly incorporated herein by reference, teach a number of split key or so-called fair cryptosystems designed to allow a secret key to be distributed to a plurality of trusted entities, such that the encrypted message is protected unless the key portions are divulged by all of the trusted entities. Thus, a secret key may be recovered, through cooperation of a plurality of parties. These methods were applied in three particular fields; law enforcement, business auctions, and financial transactions.
Essentially, the Micali systems provide that the decryption key is split between a number (n) of trusted entities, meeting the following functional criteria: (1) The private key can be reconstructed given knowledge of all n of the pieces held by the plurality of trusted entities; (2) The private key cannot be guessed at all if one only knows less than all (<n−1) of the special pieces; and (3) For i−1, . . . n, the ith special piece can be individually verified to be correct. The special pieces are defined by a simple public algorithm which itself exploits the difficulty in factoring large numbers as a basis for asymmetric security.